home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / quant.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  9KB  |  453 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    quant -
  19.  *        general median cut algorithm follows.  This is 
  20.  *    based on heckbert's median cut algoirthm.
  21.  *
  22.  *                Paul Haeberli - 1990
  23.  */
  24. #include "stdio.h"
  25. #include "quant.h"
  26.  
  27. #define MAXCOLORS     (256)
  28. #define NINCHUNK    (40)
  29. #define SPACEDIM    (64)
  30. #define NOCOLOR        (10000)
  31.  
  32. #define RDIR    (1)
  33. #define GDIR    (2)
  34. #define BDIR    (3)
  35.  
  36. typedef struct colorvol {
  37.     struct colorvol     *next;
  38.     long        rmin, rmax, rcut, rdev;
  39.     long        gmin, gmax, gcut, gdev;
  40.     long        bmin, bmax, bcut, bdev;
  41.     int         avgdev;
  42.     int            npixels;
  43.     int            splitdir;
  44.     int            number;
  45. } colorvol;
  46.  
  47. static long carray[SPACEDIM][SPACEDIM][SPACEDIM];
  48. static short iarray[SPACEDIM][SPACEDIM][SPACEDIM];
  49. static long ctab[MAXCOLORS][3];
  50. static short rbuf[MAXCOLORS];
  51. static short gbuf[MAXCOLORS];
  52. static short bbuf[MAXCOLORS];
  53. static colorvol *cvarray[MAXCOLORS];
  54. static colorvol *fvols = 0;
  55. static colorvol *root = 0;
  56. static int ncolors;
  57. static int nnodes;
  58. static int heckmode;
  59.  
  60. static clearspace()
  61. {
  62.     long i;
  63.     long *lptr;
  64.  
  65.     lptr = carray[0][0];
  66.     for(i=SPACEDIM*SPACEDIM*SPACEDIM; i--;)
  67.     *lptr++ = 0;
  68. }
  69.  
  70. static navgtospace(r, g, b)
  71. int r, g, b;
  72. {
  73.     int index, n;
  74.  
  75.     index = iarray[r][g][b];
  76.     if(index == NOCOLOR)
  77.     return;
  78.     n = carray[r][g][b];
  79.     if(n) {
  80.     r = (255*r)/(SPACEDIM-1);
  81.     g = (255*g)/(SPACEDIM-1);
  82.     b = (255*b)/(SPACEDIM-1);
  83.     ctab[index][0] += n*r;
  84.     ctab[index][1] += n*g;
  85.     ctab[index][2] += n*b;
  86.     }
  87. }
  88.  
  89. static freevol( cv )
  90. colorvol *cv;
  91. {
  92.    if( cv ) {
  93.        cv->next = fvols;
  94.        fvols = cv;
  95.    }
  96. }
  97.  
  98. static colorvol *newvol()
  99. {
  100.     colorvol *cv;
  101.     int i;
  102.  
  103.     if(!fvols) {
  104.        cv = (colorvol *)mymalloc(NINCHUNK*sizeof(colorvol));
  105.        for(i=0; i<NINCHUNK; i++)
  106.        freevol(cv++);
  107.     }
  108.     cv = fvols;
  109.     fvols = fvols->next;
  110.     return cv;
  111. }
  112.  
  113. static zaphist(hist,min,max)
  114. long hist[];
  115. long min, max;
  116. {
  117.     int i;
  118.  
  119.     for(i=min; i<=max; i++)
  120.     hist[i] = 0;
  121. }
  122.  
  123. static rangehist(hist,min,max,npix,ravg,rdev)
  124. long hist[];
  125. long min, max, npix, *ravg, *rdev; 
  126. {
  127.     int i;
  128.     long delta, avg, dev;
  129.  
  130.     avg = 0;
  131.     for(i=min; i<=max; i++)  {
  132.     avg += i*hist[i];
  133.     }
  134.     avg = avg/npix;
  135.  
  136.     dev = 0;
  137.     for(i=min; i<=max; i++) {
  138.     delta = i-avg;
  139.     dev += hist[i]*delta*delta;
  140.     }
  141.     *ravg = avg;  
  142.     *rdev = dev>>8;
  143.  
  144.     if(avg == min)
  145.     return 0;
  146.     else
  147.     return 1;
  148. }
  149.  
  150. #define FLAGMAX        (12000)
  151.  
  152. static makenode(rmin,rmax,gmin,gmax,bmin,bmax)
  153. int rmin, rmax, gmin, gmax, bmin, bmax;
  154. {
  155.     colorvol *cv, *ptr;
  156.     int Rmin, Rmax, Gmin, Gmax, Bmin, Bmax;
  157.     int r, g, b;
  158.     int rok, gok, bok;
  159.     long npixels, val;
  160.     long rhist[SPACEDIM];
  161.     long ghist[SPACEDIM];
  162.     long bhist[SPACEDIM];
  163.  
  164.     cv = newvol();
  165.  
  166.     Rmin = Gmin = Bmin = FLAGMAX;
  167.     Rmax = Gmax = Bmax = -FLAGMAX;
  168.  
  169.     zaphist(rhist,rmin,rmax);
  170.     zaphist(ghist,gmin,gmax);
  171.     zaphist(bhist,bmin,bmax);
  172.     npixels = 0;
  173.     for(b=bmin; b<=bmax; b++) {
  174.     for(g=gmin; g<=gmax; g++) {
  175.         for(r=rmin; r<=rmax; r++) {
  176.         val = carray[r][g][b];
  177.         if(val) {
  178.             if(r<Rmin)
  179.             Rmin = r;
  180.             if(g<Gmin)
  181.             Gmin = g;
  182.             if(b<Bmin)
  183.             Bmin = b;
  184.  
  185.             if(r>Rmax)
  186.             Rmax = r;
  187.             if(g>Gmax)
  188.             Gmax = g;
  189.             if(b>Bmax)
  190.             Bmax = b;
  191.             npixels+=val;
  192.             rhist[r] += val;
  193.             ghist[g] += val;
  194.             bhist[b] += val;
  195.         }
  196.         }
  197.     }
  198.     }
  199.     if(npixels == 0)
  200.     return;
  201.  
  202.     cv->npixels = npixels;
  203.     cv->rmin = Rmin;
  204.     cv->gmin = Gmin;
  205.     cv->bmin = Bmin;
  206.     cv->rmax = Rmax;
  207.     cv->gmax = Gmax;
  208.     cv->bmax = Bmax;
  209.     rok = rangehist(rhist,cv->rmin,cv->rmax,npixels,&cv->rcut,&cv->rdev);
  210.     gok = rangehist(ghist,cv->gmin,cv->gmax,npixels,&cv->gcut,&cv->gdev);
  211.     bok = rangehist(bhist,cv->bmin,cv->bmax,npixels,&cv->bcut,&cv->bdev);
  212.  
  213.     if(rok && cv->rdev>=cv->gdev && cv->rdev>=cv->bdev) 
  214.     cv->splitdir = RDIR;
  215.     else if(gok && cv->gdev>=cv->rdev && cv->gdev>=cv->bdev) 
  216.     cv->splitdir = GDIR;
  217.     else  if(bok)
  218.     cv->splitdir = BDIR;
  219.     else
  220.     cv->splitdir = 0;
  221.  
  222.     cv->avgdev = cv->rdev+cv->gdev+cv->bdev;
  223. #ifdef OLDWAY
  224.     cv->avgdev = ILUM(cv->rdev,cv->gdev,cv->bdev);
  225. #endif
  226.     cv->next = root;
  227.     root = cv;
  228.     nnodes++;
  229. }
  230.  
  231. static avgtospace(short *r, short *g, short *b, int n)
  232. {
  233.     int tr, tg, tb;
  234.     int ir, ig, ib;
  235.     int index;
  236.  
  237.     while(n--) {
  238.       tr = *r++;
  239.       tg = *g++;
  240.       tb = *b++;
  241.       ir = (SPACEDIM*tr)/256;
  242.       ig = (SPACEDIM*tg)/256;
  243.       ib = (SPACEDIM*tb)/256;
  244.     index = iarray[ir][ig][ib];
  245.     if(index == NOCOLOR) {
  246.         fprintf(stderr,"hquant: bad poop\n");
  247.         exit(1);
  248.     } else {
  249.         ctab[index][0] += tr;
  250.         ctab[index][1] += tg;
  251.         ctab[index][2] += tb;
  252.     }
  253.     }
  254. }
  255.  
  256. static divspace(cv)
  257. colorvol *cv;
  258. {
  259.     switch(cv->splitdir) {
  260.     case RDIR:
  261.         makenode(cv->rmin,cv->rcut-1,cv->gmin,cv->gmax,cv->bmin,cv->bmax); 
  262.         makenode(cv->rcut,cv->rmax,  cv->gmin,cv->gmax,cv->bmin,cv->bmax); 
  263.         break;
  264.     case GDIR:
  265.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gcut-1,cv->bmin,cv->bmax); 
  266.         makenode(cv->rmin,cv->rmax,cv->gcut,cv->gmax,  cv->bmin,cv->bmax); 
  267.         break;
  268.     case BDIR:
  269.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gmax,cv->bmin,cv->bcut-1); 
  270.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gmax,cv->bcut,cv->bmax  ); 
  271.         break;
  272.     default:
  273.         fprintf(stderr,"quant: divspace: bad poop %d\n",cv->splitdir);
  274.         exit(1);
  275.     }
  276.     nnodes--;
  277.     cv->npixels = 0;
  278.     cv->avgdev = 0;
  279. }
  280.  
  281. /*
  282.  *    gammawarp stuff follows
  283.  *
  284.  *
  285.  */
  286. static float curgamma;
  287. static short gamtab[256];
  288.  
  289. static gammawarp(sbuf,gam,n)
  290. short *sbuf;
  291. float gam;
  292. int n;
  293. {
  294.     int i;
  295.     float f;
  296.  
  297.     if(gam!=curgamma) {
  298.     for(i=0; i<256; i++) 
  299.         gamtab[i] = 255*pow(i/255.0,gam)+0.5;
  300.     curgamma = gam;
  301.     }
  302.     while(n--) {
  303.     *sbuf = gamtab[*sbuf];
  304.     sbuf++;
  305.     }
  306. }
  307.  
  308. static lumwarp(r,g,b,gamma)
  309. short *r, *g, *b;
  310. float gamma;
  311. {
  312.     int max, nmax;
  313.  
  314.     max = *r;
  315.     if(*g>max)
  316.     max = *g;
  317.     if(*b>max)
  318.     max = *b;
  319.     if(max>0) {
  320.     nmax = 255*pow(max/255.0,gamma)+0.49;
  321.     *r = (nmax * *r)/max;
  322.     *g = (nmax * *g)/max;
  323.     *b = (nmax * *b)/max;
  324.     } else {
  325.     *r = 0;
  326.     *g = 0;
  327.     *b = 0;
  328.     }
  329. }
  330.  
  331. void optmapbegin(int nc, int mode)
  332. {
  333.     ncolors = nc;
  334.     if(ncolors>MAXCOLORS) {
  335.     fprintf(stderr,"quant: num colors exceeds %d\n",MAXCOLORS);
  336.     exit(1);
  337.     }
  338.     heckmode = mode;
  339.     clearspace();
  340. }
  341.  
  342. void optmapadd( short *r,  short *g,  short *b, int n)
  343. {
  344.     int ir, ig, ib;
  345.  
  346.     while(n--) {
  347.       ir = (SPACEDIM*(*r++))/256;
  348.       ig = (SPACEDIM*(*g++))/256;
  349.       ib = (SPACEDIM*(*b++))/256;
  350.     carray[ir][ig][ib]++;
  351.     }
  352. }
  353.  
  354. cmap *optmapend( void )
  355. {
  356.     int i, r, g, b;
  357.     int totcolors, bigest;
  358.     colorvol *bigcv, *cv;
  359.  
  360. /* repeat division of the smallest piece for ncolors */
  361.     root = NULL;
  362.     nnodes = 0;
  363.     makenode(0,SPACEDIM-1,0,SPACEDIM-1,0,SPACEDIM-1); 
  364.  
  365.     if(heckmode) {
  366.     while(nnodes<ncolors) {
  367.         bigcv = 0;
  368.         bigest = 0;
  369.         cv = root;
  370.         while(cv) {
  371.         if(cv->splitdir && cv->npixels>bigest) {
  372.              bigcv = cv;
  373.              bigest = cv->npixels;
  374.         }
  375.         cv = cv->next;
  376.         }
  377.         if(bigcv)
  378.         divspace(bigcv);
  379.         else {
  380.         fprintf(stderr,"N colors reduced to %d from %d\n",nnodes,ncolors);
  381.         ncolors = nnodes;
  382.         break;
  383.         }
  384.     }
  385.     } else {
  386.     while(nnodes<ncolors) {
  387.         bigcv = 0;
  388.         bigest = 0;
  389.         cv = root;
  390.         while(cv) {
  391.         if(cv->splitdir && cv->avgdev>bigest) {
  392.              bigcv = cv;
  393.              bigest = cv->avgdev;
  394.         }
  395.         cv = cv->next;
  396.         }
  397.         if(bigcv)
  398.         divspace(bigcv);
  399.         else {
  400.         fprintf(stderr,"Ncolor reduced to %d from %d\n",nnodes,ncolors);
  401.         ncolors = nnodes;
  402.         break;
  403.         }
  404.     }
  405.     }
  406.  
  407. /* clear the iarray to NOCOLOR */
  408.     for(r=0; r<SPACEDIM; r++)
  409.     for(g=0; g<SPACEDIM; g++)
  410.         for(b=0; b<SPACEDIM; b++) 
  411.         iarray[r][g][b] = NOCOLOR;
  412.  
  413. /* set the color numbers for all the volumes */
  414.     cv=root;
  415.     totcolors = 0;
  416.     while(cv) {
  417.     if(cv->npixels) {
  418.         cvarray[totcolors] = cv;
  419.         cv->number = totcolors;
  420.         for(r=cv->rmin; r<=cv->rmax; r++)
  421.         for(g=cv->gmin; g<=cv->gmax; g++)
  422.             for(b=cv->bmin; b<=cv->bmax; b++) 
  423.             iarray[r][g][b] = totcolors;
  424.         totcolors++;
  425.     }
  426.     cv = cv->next;
  427.     }
  428.  
  429. /* read the input image again, finding average colors */
  430.  
  431.     for(i=0; i<ncolors; i++) {
  432.     ctab[i][0] = 0;
  433.     ctab[i][1] = 0;
  434.     ctab[i][2] = 0;
  435.     }
  436.     for(b=0; b<SPACEDIM; b++) {
  437.     for(g=0; g<SPACEDIM; g++) {
  438.         for(r=0; r<SPACEDIM; r++) {
  439.         navgtospace(r,g,b);
  440.         }    
  441.     }    
  442.     }    
  443.     for(i=0; i<ncolors; i++) {
  444.     ctab[i][0] /= cvarray[i]->npixels;
  445.     ctab[i][1] /= cvarray[i]->npixels;
  446.     ctab[i][2] /= cvarray[i]->npixels;
  447.     rbuf[i] = ctab[i][0];
  448.     gbuf[i] = ctab[i][1];
  449.     bbuf[i] = ctab[i][2];
  450.     }
  451.     return newcmap(rbuf,gbuf,bbuf,0,ncolors);
  452. }
  453.